package com.hqq.exercise.tree;

import java.util.Arrays;

/**
 * ConstructBiTree 重建二叉树
 * 题目描述:
 * 输入二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设前序遍历和中序遍历结果中都不包含重复的数字
 * 输入样例:
 * 前序遍历序列{1,2,4,7,3,5,6,8}
 * 中序遍历序列{4,7,2,1,5,3,8,6}
 * 输出样例:
 * {1,2,3,4,5,6,7,8}
 * --------1
 * -----2     3
 * ---4     5   6
 * --7      8
 * Created by heqianqian on 2017/8/10.
 */
public class ConstructBiTree {

    /**
     * 重建二叉树
     *
     * @param preOrder 前序遍历数组
     * @param midOrder 中序遍历数组
     * @return 二叉树
     */
    public static TreeNode constructBiTree(int[] preOrder, int[] midOrder) {
        TreeNode root = new TreeNode();
        /*判断非法输入*/
        if (preOrder == null || midOrder == null || (preOrder.length != midOrder.length)) {
            throw new IllegalArgumentException("参数不合法");
        }
        for (int i = 0; i < midOrder.length; i++) {
            if (midOrder[i] == preOrder[0]) {//找到根节点
                root.val = midOrder[i];
                //遍历左子树
                root.left = constructBiTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                        Arrays.copyOfRange(midOrder, 0, i));
                //遍历右子树
                root.right = constructBiTree(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                        Arrays.copyOfRange(midOrder, i + 1, midOrder.length));
            }
        }
        return root;
    }
}
